package com.mkx.bloomfilter;

import java.util.BitSet;

/**
 * 布隆过滤器实现 - 优化版本
 * 布隆过滤器是一种空间效率很高的概率性数据结构，用于判断一个元素是否在一个集合中。
 * 特点是：可能会误判（即返回元素存在但实际不存在），但不会漏判（即返回元素不存在则肯定不存在）。
 */
public class BloomFilter<T> {
    // 位数组，用于存储元素的哈希值对应的位
    private final BitSet bitSet;
    
    // 位数组大小
    private final int bitSetSize;
    
    // 哈希函数生成器
    private final HashFunctionGenerator hashFunctionGenerator;
    
    // 哈希函数数量
    private final int hashFunctionCount;
    
    /**
     * 构造函数，根据预期元素数量和期望误判率计算最佳参数
     * @param expectedElements 预期要存储的元素数量
     * @param falsePositiveRate 期望的误判率（0-1之间）
     */
    public BloomFilter(int expectedElements, double falsePositiveRate) {
        this(expectedElements, falsePositiveRate, System.nanoTime());
    }
    
    /**
     * 构造函数，使用指定的随机种子
     * @param expectedElements 预期要存储的元素数量
     * @param falsePositiveRate 期望的误判率（0-1之间）
     * @param randomSeed 随机种子，用于生成可重复的哈希函数
     */
    public BloomFilter(int expectedElements, double falsePositiveRate, long randomSeed) {
        if (expectedElements <= 0) {
            throw new IllegalArgumentException("Expected elements must be positive");
        }
        if (falsePositiveRate <= 0 || falsePositiveRate >= 1) {
            throw new IllegalArgumentException("False positive rate must be between 0 and 1");
        }
        
        // 计算最佳位数组大小：m = -n*ln(p)/(ln(2)^2)，其中n是预期元素数，p是误判率
        this.bitSetSize = calculateBitSetSize(expectedElements, falsePositiveRate);
        
        // 计算最佳哈希函数数量：k = (m/n)*ln(2)
        this.hashFunctionCount = calculateHashFunctionCount(bitSetSize, expectedElements);
        
        // 初始化位数组
        this.bitSet = new BitSet(bitSetSize);
        
        // 初始化哈希函数生成器
        this.hashFunctionGenerator = new HashFunctionGenerator(hashFunctionCount, randomSeed);
    }
    
    /**
     * 添加元素到布隆过滤器 - 高性能优化版本
     * 使用位操作优化和缓存机制提高性能
     * @param element 要添加的元素
     */
    public void add(T element) {
        if (element == null) {
            throw new NullPointerException("Element cannot be null");
        }
        
        // 使用优化的双重哈希技术生成哈希索引
        int[] hashValues = getHashIndices(element);
        
        // 批量设置位，减少方法调用开销
        // BitSet.set()方法已经是高效的，但我们可以考虑在未来版本中使用更底层的位操作
        for (int index : hashValues) {
            bitSet.set(index);
        }
    }
    
    /**
     * 判断元素是否可能在布隆过滤器中 - 优化版本
     * @param element 要检查的元素
     * @return 如果元素可能存在返回true，如果元素肯定不存在返回false
     */
    public boolean mightContain(T element) {
        if (element == null) {
            throw new NullPointerException("Element cannot be null");
        }
        
        // 优化：使用双重哈希技术减少哈希计算次数
        int[] hashValues = getHashIndices(element);
        
        // 检查所有哈希函数对应的位是否都被设置
        for (int index : hashValues) {
            if (!bitSet.get(index)) {
                // 如果有任何一个位未被设置，则元素肯定不存在
                return false;
            }
        }
        // 所有位都被设置，元素可能存在（存在误判可能）
        return true;
    }
    
    // 哈希索引缓存，用于重复元素的快速查找
    private final ThreadLocal<int[]> hashIndexCache = ThreadLocal.withInitial(() -> null);
    
    // 缓存的哈希值，用于检测重复元素
    private final ThreadLocal<Object> lastElementCache = ThreadLocal.withInitial(() -> null);
    
    /**
     * 计算元素的哈希索引位置 - 高性能双重哈希技术
     * 使用增强的双重哈希算法，减少哈希计算次数，提高缓存效率
     * @param element 输入元素
     * @return 哈希索引数组
     */
    private int[] getHashIndices(T element) {
        // 检查是否是相同的元素，如果是则重用之前的哈希索引
        if (element.equals(lastElementCache.get())) {
            int[] cachedIndices = hashIndexCache.get();
            if (cachedIndices != null) {
                return cachedIndices;
            }
        }
        
        int[] indices = new int[hashFunctionCount];
        
        // 使用优化的双重哈希技术，只计算一次哈希值
        // 基于Kirsch-Mitzenmacher优化的双重哈希
        int hash = Math.abs(element.hashCode() * 0x9E3779B9);
        int step = Math.abs((hash >> 16) | (hash << 16)) | 1; // 确保step为奇数
        
        // 生成多个哈希索引
        for (int i = 0; i < hashFunctionCount; i++) {
            hash = Math.abs((hash + step) % bitSetSize);
            indices[i] = hash;
        }
        
        // 更新缓存
        hashIndexCache.set(indices);
        lastElementCache.set(element);
        
        return indices;
    }
    
    /**
     * 批量添加多个元素 - 优化版本
     * 减少缓存更新的频率，提高批量操作性能
     * @param elements 元素集合
     */
    public void addAll(Iterable<? extends T> elements) {
        if (elements == null) {
            throw new IllegalArgumentException("Elements cannot be null");
        }
        
        // 清除缓存，避免批量操作中缓存干扰
        boolean cacheCleared = false;
        for (T element : elements) {
            if (!cacheCleared) {
                // 批量操作前清除缓存，避免缓存频繁更新
                hashIndexCache.remove();
                lastElementCache.remove();
                cacheCleared = true;
            }
            add(element);
        }
    }
    
    /**
     * 批量添加数组中的元素
     * @param elements 元素数组
     */
    public void addAll(T[] elements) {
        if (elements == null) {
            throw new IllegalArgumentException("Elements array cannot be null");
        }
        for (T element : elements) {
            add(element);
        }
    }
    
    /**
     * 批量检查元素 - 新增方法
     * @param elements 要检查的元素数组
     * @return 每个元素是否可能存在的布尔数组
     */
    public boolean[] mightContainAll(T[] elements) {
        if (elements == null) {
            throw new IllegalArgumentException("Elements array cannot be null");
        }
        
        boolean[] results = new boolean[elements.length];
        for (int i = 0; i < elements.length; i++) {
            results[i] = mightContain(elements[i]);
        }
        return results;
    }
    
    /**
     * 清除布隆过滤器中的所有元素
     */
    public void clear() {
        bitSet.clear();
    }
    
    /**
     * 获取位数组大小
     * @return 位数组大小
     */
    public int getBitSetSize() {
        return bitSetSize;
    }
    
    /**
     * 获取哈希函数数量
     * @return 哈希函数数量
     */
    public int getHashFunctionCount() {
        return hashFunctionCount;
    }
    
    /**
     * 获取布隆过滤器中设置为1的位数 - 新增方法
     * @return 设置为1的位数
     */
    public int getBitCount() {
        return bitSet.cardinality();
    }
    
    /**
     * 估算当前误判率 - 新增方法
     * @param elementCount 已添加的元素数量
     * @return 当前误判率估算值
     */
    public double estimateFalsePositiveRate(int elementCount) {
        // 使用布隆过滤器误判率公式: (1 - e^(-k*n/m))^k
        // 其中k是哈希函数数量，n是元素数量，m是位数组大小
        double p = Math.pow(1 - Math.exp(-hashFunctionCount * elementCount / (double) bitSetSize), hashFunctionCount);
        return p;
    }
    
    /**
     * 计算最佳位数组大小
     */
    private int calculateBitSetSize(int expectedElements, double falsePositiveRate) {
        // m = -n*ln(p)/(ln(2)^2)
        double size = -expectedElements * Math.log(falsePositiveRate) / (Math.log(2) * Math.log(2));
        return Math.max(1, (int) Math.ceil(size));
    }
    
    /**
     * 计算最佳哈希函数数量
     */
    private int calculateHashFunctionCount(int bitSetSize, int expectedElements) {
        // k = (m/n)*ln(2)
        double count = (bitSetSize * Math.log(2)) / expectedElements;
        return Math.max(1, (int) Math.ceil(count));
    }
    
    /**
     * 获取当前的哈希函数生成器
     * @return 哈希函数生成器
     */
    public HashFunctionGenerator getHashFunctionGenerator() {
        return hashFunctionGenerator;
    }
}